1. Field of the Invention
The invention relates to a method and apparatus for decoding compressed image data, more particularly to a method and apparatus for decoding compressed image data and capable of preventing error propagation.
2. Description of the Related Art
Multimedia has become a widely used data format in computer and communication systems. However, multimedia data is very large in general so as to result in a heavy burden for storage and transmission. In order to reduce the memory space for storage and the channel bandwidth for transmission, data compression is necessary.
In a conventional compression algorithm, such as a run-length encoding algorithm, different code types and a line-end code are defined according to the following rules:                1. 1 to 3 continuous pixels with the same pixel data can be encoded into a code type 0 that has a 4-bit code length, as shown in Table 1 of FIG. 1.        2. 4 to 15 continuous pixels with the same pixel data can be encoded into a code type 1 that has an 8-bit code length, as shown in Table 2 of FIG. 2.        
3. 16 to 63 continuous pixels with the same pixel data can be encoded into a code type 2 that has a 12-bit code length, as shown in Table 3 of FIG. 3.                4. 64 to 255 continuous pixels with the same pixel data can be encoded into a code type 3 that has a 16-bit code length, as shown in Table 4 of FIG. 4.        5. Continuous pixels with the same pixel data present at the end of a pixel line can be encoded into a line-end code that has a 16-bit code length, as shown in Table 5 of FIG. 5.        6. After a data line compressed in accordance with the above rules has been completed, a 4-bit dummy code, such as “0000” or “1111”, may be inserted for byte alignment.        
In the above-described run-length encoding algorithm, a data line must have byte alignment, i.e., the data line has a code length that is a multiple of 8 bites. When a data line compressed according to the rules 1 to 5 includes x code type 0 (4-bit code length, x is an integer not less than zero), y code type 1 (8-bit code length, y is an integer not less than zero), z code type 2 (12-bit code length, z is an integer not less than zero), u code type 3 (16-bit code length, u is an integer not less than zero) and a line-end code (16-bit code length), the data line has a code length equal to 4x+8y+12z+16u+16=4*(x+2y+3z+4u+4) bits, and rule 6 can be applied to ensure that the code length of the data line is a multiple of 8 bits.
According to the above rules, for example, if there are 2 continuous pixels with the same pixel data of “01” (0101), the pixels (0101) can be encoded into “1001” according to the code type 0 shown in FIG. 1. If there are 6 continuous pixels with the same pixel data of “01”, the pixels can be encoded into “00011001” according to the code type 1 shown in FIG. 2. If there are 63continuous pixels with the same pixel data of “01”, the pixels of 126 bits can be encoded into “000011111101” (12 bits) according to the code type 2 shown in FIG. 3. If there are 255 continuous pixels with the same pixel data of “01”, the pixels of 510 bits can be encoded into “0000001111111101”(16 bits) according to the code type 3 shown in FIG. 4. If there are a plurality of continuous pixels from a current pixel to the end of a pixel line with the same pixel data of “01”, the pixels can be encoded into “0000000000000001” (16 bits) according to the line-end code shown in FIG. 5.
In summary, the aforesaid run-length encoding algorithm has the following properties:                1. Each of the code types has a specific code length.        2. Since a line-end code is present at the end of each data line, the compression algorithm is line-based.        3. During the compression process, a proper code type can be used to represent a specific pixel combination. Accordingly, during the decompression process, an input codeword must be one of the code types and the line-end code when the input codeword is not corrupted.        
FIG. 6 illustrates a conventional run-length decoder 1 for decoding an image data block that has a plurality of data lines compressed into code word streams in accordance with the above-described run-length encoding algorithm. The conventional run-length decoder 1 includes a shifter 11, a codeword comparator 12, a code interpreter 13, and a shifter controller 14.
The shifter 11 has a codeword input for receiving a 32-bit segment of the codeword streams, and a codeword output 112 for outputting a 16-bit part of the 32-bit segment received thereby.
The codeword comparator 12 is connected to the codeword output 112 and is operable so as to orderly and continuously analyze the 16-bit part to verify presence of one of the code types (code type 0, code type 1, code type 2 and code type 3) and the line-end code therein. The codeword comparator 12 outputs one of the code types and the line-end code upon detecting the presence of said one of the code types and the line-end in the 16-bit part.
The code interpreter 13 is connected to the codeword comparator 12 and is operable so as to interpret said one of the code types and the line-end code from the codeword comparator 12 in accordance with the run-length encoding algorithm to generate a decompressed output.
The shifter controller 14 is connected to the shifter 11 and the codeword comparator 12. The shifter controller 14 controls the shifter 11 to update the 16-bit part by discarding the detected one of the code types and the line-end code and by appending a succeeding P-bit part of the 32-bit segment to remainder of the 16-bit part. The P-bit part has a code length equal to that of the detected one of the code types and the line-end code. The shifter 11 generates a request for updating the 32-bit segment when an analyzed length thereof is equal to 16. As such, when the codeword comparator 12 outputs a code type 0, the 16-bit part is updated by discarding the code type 0 therefrom and by appending a succeeding 4-bit part of the 32-bit segment to the remainder of the 16-bit part. When the codeword comparator 12 outputs a code type 1, the 16-bit part is updated by discarding the code type 1 therefrom and by appending a succeeding 8-bit part of the 32-bit segment to the remainder of the 16-bit part. When the codeword comparator 12 outputs a code type 2, the 16-bit part is updated by discarding the code type 2 therefrom and by appending a succeeding 12-bit part of the 32-bit segment to the remainder of the 16-bit part. When the codeword comparator 12 outputs a code type 3, the shifter 11 generates a request for updating the 32-bit segment by discarding the analyzed first 16 bits therefrom and by appending 16 bits of the codeword streams to the second 16 bits of the 32-bit segment, and the 16-bit part is updated with a corresponding part of the updated 32-bit segment.
In the following example, the conventional run-length decoder 1 is used for decoding a 100-pixel image data line compressed into a codeword stream. The codeword stream is “1100-00011101-000001000010-0000 000100000011-0000000000000010”.
The decompression process of the data line is as follows:                1. Initially, the first 32 bits (“1100-00011101-000001000010-00000001”) of the codeword stream are received by the shifter 11 and serves as the 32-bit segment. The shifter 11 outputs the first 16 bits (“1100-00011101-0000”) of the 32-bit segment that serves as the 16-bit part to the codeword comparator 12. The codeword comparator 12 verifies the presence of a code type 0 (“1100”) in the 16-bit part, and outputs the code type 0 (“1100”). The code interpreter 13 interprets the code type 0 from the codeword comparator 12 in accordance with the above-described run-length encoding algorithm so as to generate a decompressed output corresponding to the code type 0 (“1100”) that has 3 continuous pixels (i.e., pixel length=3) with the same pixel data of “00”. The shifter controller 14 controls the shifter 11 to update the 16-bit part (“1100-00011101-0000”) by discarding the code type 0 (“1100”) from the 16-bit part (“1100-00011101-0000”) and by appending a succeeding 4-bit part (“0100”) of the 32-bit segment to the remainder of the 16-bit part (“00011101-0000”) such that the 16-bit part becomes “00011101-00000100”.        2. Subsequently, the codeword comparator 12 continuous analysis of the 16-bit part (“00011101-0000 0100”), verifies presence of a code type 1 (“00011101”) in the 16-bit part, and outputs the code type 1 (“00011101”). The code interpreter 13 interprets the code type 1 from the codeword comparator 12 in accordance with the above-described run-length encoding algorithm so as to generate a decompressed output corresponding to the code type 1 (“00011101”) that has 7 continuous pixels (i.e., pixel length=7) with the same pixel data of “01”. The shifter controller 14 controls the shifter 11 to update the 16-bit part (“00011101-00000100”) by discarding the code type 1 (“00011101”) from the 16-bit part (“00011101-00000100”) and by appending a succeeding 8-bit part (“00100000”) of the 32-bit segment to the remainder of the 16-bit part (“00000100”) such that the 16-bit part becomes “000001000010-0000”.        3. Then, the codeword comparator 12 continuous analysis of the 16-bit part (“000001000010-0000”) verifies presence of a code type 2 (“000001000010”) in the 16-bit part, and outputs the code type 2 (“000001000010”). The code interpreter 13 interprets the code type 2 from the codeword comparator 12 in accordance with the above-described run-length encoding algorithm so as to generate a decompressed output corresponding to the code type 2 (“000001000010”) that has 16 continuous pixels (i.e., pixel length=16) with the same pixel data of “10”. Since the analyzed length of the current 32-bit segment is equal to 24 (4+8+12), the shifter 11 generates a request for updating the 32-bit segment by discarding the first 16 bits (“1100-00011101-0000”) from the 32-bit segment and by appending a succeeding 16 bits (“00000011-00000000”) of the codeword stream to the remainder of the 32-bit segment (“01000010-00000001”) such that the 32-bit segment becomes “01000010-0000 000100000011-00000000”. The shifter controller 14 controls the shifter 11 to update the 16-bit part (“000001000010-0000”) by discarding the code type 2 (“000001000010”) from the 16-bit part (“000001000010-0000”) and by appending a succeeding 12-bit part (“000100000011”) of the 32-bit segment to the remainder of the 16-bit part (“0000”) such that the 16-bit part becomes “0000000100000011”.        4. Thereafter, the codeword comparator 12 continuous analysis of the 16-bit part (“10000000100000011”), verifies presence of a code type 3 (“0000000100000011”) in the 16-bit part, and outputs the code type 3 (“0000000100000011”). The code interpreter 13 interprets the code type 3 from the codeword comparator 12 in accordance with the above-described run-length encoding algorithm so as to generate a decompressed output corresponding to the code type 3 (“0000000100000011”) that has 64 continuous pixels (i.e., pixel length=64) with the same pixel data of “11”. Since the analyzed length of the current 32-bit segment is equal to 16, the shifter 11 once again generates a request for updating the 32-bit segment according to the previously described manner such that the 32-bit segment becomes “00000011-0000000000000010-xxxxxxxx” (“x” means do not care). The shifter controller 14 controls the shifter 11 to update the 16-bit part (“0000000100000011”) by discarding the code type 3 (“0000000100000011”) from the 16-bit part such that the 16-bit part becomes “0000000000000010”.        5. Eventually, the codeword comparator 12 verifies the presence of a line-end code (“0000000000000010”) in the 16-bit part, and outputs the line-end code (“0000000000000010”). The code interpreter 13 interprets the line-end code from the codeword comparator 12 in accordance with the above-described run-length algorithm so as to generate a decompressed output corresponding to the line-end code (“0000000000000010”) that has 10 (equal to 100−3−7−16−64) continuous pixels with the same pixel data of “10”. As such, decompression of the data line is thus completed.        
Due to the presence of noise during transmission or storage, the compressed codeword stream may be corrupted such that the codeword comparator 12 is unable to verify the presence of a correct one of the code types and the decoder 1 thus fails to output a correct decompressed output. It is noted that when the compressed data is corrupted, the conventional run-length decoder 1 cannot continuously decode the compressed data. Furthermore, when the codeword comparator 12 is unable to verify the presence of the correct one of the code types, the shifter controller 14 will be unable to properly control the shifter 11 to update the 16-bit part, thereby resulting in an adverse affect on a succeeding decompressed output, which arises in error propagation.